package com.chj.leetcode.tijie0to50;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code42_TrappingRainWater {
	public static int maxRecSize(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}

		int maxArea = getNearLessNoRepeat(height);
		return maxArea;
	}

	public static int getNearLessNoRepeat(int[] arr) {

		int maxArea = 0;
		int len = 0;
		int sub = 0;
		Deque<Deque<Integer>> stack = new ArrayDeque<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i]
			while (!stack.isEmpty() && arr[stack.peek().getFirst()] < arr[i]) {
				// 当前弹出的东西 ： popIndex -> arr[popIndex]
//				int popIndex = stack.pop();
				Deque<Integer> popQueue = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().getLast();
//				res[popIndex][0] = leftLessIndex;
//				res[popIndex][1] = i;
				if (leftLessIndex == -1) {
					continue;
				}

				for (Integer popIndex : popQueue) {
					sub = Math.min(arr[leftLessIndex], arr[i]) - arr[popIndex];
					len = i - leftLessIndex + 1 - 2;
					maxArea = len * sub + maxArea;
					break;
				}
			}

			if (!stack.isEmpty() && arr[stack.peek().getFirst()] == arr[i]) {
				stack.peek().addLast(Integer.valueOf(i));
			} else {
				Deque<Integer> queue = new ArrayDeque<>();
				queue.add(Integer.valueOf(i));
				stack.push(queue);
			}
		}
		return maxArea;
	}

	public static void main(String[] args) {
		int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		System.out.println(maxRecSize(arr));
	}
}
